package com.yoshino.leetcode.interview150.number;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Optional;

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0 || ((x & 1) == 0 && x != 0)) {
            return false;
        }
        // 121 1221
        // 反转一半
        int temp = x, res = 0;
        if (x < 10) {
            return true;
        }
//        while (temp != 0) {
//            res = res * 10 + temp % 10;
//            temp /= 10;
//        }
        while (x > res) {
            res = res * 10 + x % 10;
            x /= 10;
        }
        return x == res || res / 10 == x;
    }

    public int[] plusOne(int[] digits) {
//        int carry = 1;
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] != 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
//            if (carry == 0) {
//                break;
//            }
//            digits[i] += carry;
//            carry = 0;
//            if (digits[i] == 10) {
//                digits[i] = 0;
//                carry = 1;
//            }
        }
//        if (carry == 1) {
            int[] res = new int[digits.length + 1];
            System.arraycopy(digits, 0, res, 1, digits.length);
            res[0] = 1;
            return res;
//        }
//        return digits;
    }

    public int trailingZeroes(int n) {
        // 组成几个 10
        int five = 0, temp;
//        for (int i = 2; i < n + 1; i++) {
//            temp = i;
//            while (temp % 5 == 0) {
//                five++;
//                temp /= 5;
//            }
//        }
        while (n > 0) {
            n /= 5;
            five += n;
        }
        return five;
    }

    public int mySqrt(int x) {
//        if (x == 1) {
//            return 1;
//        }
//        // 二分查找
//        int left = 0, right = x, mid;
//        while (left < right) {
//            mid = left + (right - left) / 2;
//            if (x / mid < mid) {
//                right = mid;
//            } else {
//                left = mid;
//            }
//        }
//        return left;
        int left = 0, right = x, res = 0, mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if ((long)mid * mid <= x) {
                res = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;
    }

    public double myPow(double x, int n) {
        long N = n;
        return N < 0 ? 1.0 / quickPow(x, -N) : quickPow(x, N);
    }

    private double quickPow(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickPow(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }

    public int maxPoints(int[][] points) {
        if (points.length < 3) {
            return points.length;
        }
        int res = 0;
        // 先固定两个点，确认一条线，再找线上的点
        for (int i = 0; i < points.length - 2; i++) {
            for (int j = i + 1; j < points.length - 1; j++) {
                int count = 2;
                int x1 = points[i][0] - points[j][0];
                int y1 = points[i][1] - points[j][1];
                for (int k = j + 1; k < points.length; k++) {
                    int x2 = points[i][0] - points[k][0];
                    int y2 = points[i][1] - points[k][1];
                    if (x2 * y1 == x1 * y2) {
                        count++;
                    }
                }
                res = Math.max(res, count);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        new Solution().mySqrt(2147395599);
    }
}